package training;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_5_24_Training {
    //找出星型图的中心节点
    public int findCenter(int[][] edges) {
        int n = edges.length+1; //n个节点
        int[] node = new int[n];
        for(int[] e : edges){
            int a = e[0];
            int b = e[1];
            node[a-1]++;
            node[b-1]++;
        }
        for(int i=0;i<n;i++){
            if(node[i] == n-1){
                return i+1;
            }
        }
        return -1;
    }

    //向数组中追加 K 个整数
    public long minimalKSum(int[] nums, int k) {
        long res = 0;
        long nk = k;
        int[] newNums = new int[nums.length + 1];
        for(int i = 1; i < newNums.length; i++){
            newNums[i] = nums[i - 1];
        }
        Arrays.sort(newNums);

        for(int i = 0; i < newNums.length - 1; i++){
            //相邻两个数之间的区间起点和终点
            long start = newNums[i] + 1;
            long end = newNums[i + 1] - 1;
            //例如[1,2]这种中间没有数可累加
            if(start > end){
                continue;
            }
            //区间数字个数
            long count = end - start + 1;
            //区间数字个数多于还要加的数个数k
            if(k <= count){
                //只加该区间前k个数
                res += (start + start + k - 1) * k / 2;
                return res;
            }else{
                //区间所有数累和
                res += (start + end) * count / 2;
            }
            k -= count;
        }

        //数组遍历完以后，还有要追加的数
        long start = newNums[newNums.length - 1] + 1;
        res += (start + start + k - 1) * k / 2;

        return res;
    }
}
